package com.db.javaschool.kislros;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class TinyHastable {

	public static final String PRINT_NEAREST_PRIME_TIME = "com.db.javaschool.kislros.tinyhashtable.print_nearest_prime_time";
	private int[] keys, values;
	private int capacity;
	private final int NULL_KEY;
	private final int NULL_VALUE;
	private int size;
	
	private boolean isPrime(int x) {
		if (x < 2) return false;
		if (x == 2) return true;
		else if (x % 2 == 0) return false;
		for (int i = 3; i*i <= x; i += 2) {
			if (x % i == 0) return false;
		}
		return true;
	}
	
	/*
	 * At average this operation is cheap - probability of N to be prime is 1 / ln(N), and
	 * Euler function estimation is O(N), so it'll take O(N/ln(N)) to findNearestPrime even
	 * by this inefficient way.
	 */
	private int findNearestPrime(int from) {
		int i = from+1;
		while (!isPrime(i))
			++i;
		return i;
	}
	
	/**
	 * Creates a hashtable.
	 * @param initialCap Capacity for hashtable. Must be positive number. The table will contain not more than that number of elements.
	 * @param nullKey The key that assumed to be null-value and will never be used as ordinal key.
	 * @param defaultValue Will be returned when trying to get not existing key.
	 */
	public TinyHastable(int initialCap, int nullKey, int defaultValue) {
		if (initialCap <= 0)
			throw new IllegalArgumentException("Capacity must be positive number.");
		
		long t = System.currentTimeMillis();
		capacity = findNearestPrime(initialCap);
		if ("true".equals(System.getProperty(PRINT_NEAREST_PRIME_TIME)))
			System.out.println("Finding nearest prime took " + (t - System.currentTimeMillis()) + " ms.");
		
		keys = new int[capacity];
		values = new int[capacity];
		NULL_KEY = nullKey;
		NULL_VALUE = defaultValue;
		size = 0;
		Arrays.fill(keys, NULL_KEY);
		Arrays.fill(values, NULL_VALUE);
	}
	
	public TinyHastable(int initialCap) {
		this(initialCap, -1, -1);
	}
	
	private int bucket(int k) {
		return Math.abs(k % capacity);
	}
	
	/**
	 * Adds entry into hashtable.
	 * @param k Key of entry. Entry won't be added if key is <code>nullKey</code>
	 * @param v Value of entry.
	 * @return <code>this</code> instance.
	 * @throws ArrayIndexOutOfBoundsException Throws exception when capacity is overflowed.
	 */
	public TinyHastable put(int k, int v) {
		if (k == NULL_KEY)
			return this;
		if (size == capacity)
			throw new ArrayIndexOutOfBoundsException("Too many entries for hashtable");
		
		int b = bucket(k);
		while (keys[b] != NULL_KEY && keys[b] != k) {
			++b;
			if (b == capacity) b = 0;
		}
		keys[b] = k;
		values[b] = v;
		++size;
		return this;
	}
	
	/**
	 * Returns value for given key.
	 * @param k Given key.
	 * @return Value for given key or <code>defaultValue</code> if it doesn't exist or key is equal to <code>nullKey</code>.
	 */
	public int get(int k) {
		if (k == NULL_KEY)
			return NULL_VALUE;

		int b = bucket(k);
		while (keys[b] != NULL_KEY && keys[b] != k) {
			++b;
			if (b == capacity) b = 0;
		}
		return keys[b] != NULL_KEY ? values[b] : NULL_VALUE;
	}
	
	/**
	 * Checks key existence in table.
	 * @param k Key to check.
	 * @return <code>true</code> if exists, <code>false</code> otherwise.
	 */
	public boolean exists(int k) {
		return get(k) != NULL_VALUE;
	}
	
	/**
	 * Clears the whole table.
	 */
	public void clear() {
		for (int i = 0; i < capacity; ++i)
			keys[i] = NULL_KEY;
		size = 0;
	}
	
	public static void main(String[] args) {
		System.out.println("TinyHashtable:");
		Runtime rt = Runtime.getRuntime();
		long memBefore = rt.totalMemory() - rt.freeMemory();
		long tBefore = System.currentTimeMillis();
		TinyHastable sh = new TinyHastable(1030000, -1, -1);
		long tAfter = System.currentTimeMillis();
		System.out.println("Construction took: " + (tAfter - tBefore) + " ms.");
		
		Random rnd = new Random(42);
		int[] randomBuffer = new int[1_000_000];
		for (int i = 0; i < 1_000_000; ++i)
			randomBuffer[i] = Math.abs(rnd.nextInt());
		
		tBefore = System.currentTimeMillis();
		for (int i = 0; i < 1_000_000; ++i)
			sh.put(randomBuffer[i], randomBuffer[i]);
		tAfter = System.currentTimeMillis();
		long memAfter = rt.totalMemory() - rt.freeMemory();
		System.out.println("Used memory estimation: " + (memAfter - memBefore) +
				", average usage per entry: " + (memAfter - memBefore) / 1E6 + " bytes");
		System.out.println("Put average time: " + (tAfter - tBefore) + " ns.");

		tBefore = System.currentTimeMillis();
		for (int i = 0; i < 1_000_000; ++i)
			sh.get(randomBuffer[i]);
		tAfter = System.currentTimeMillis();
		System.out.println("Get average time: " + (tAfter - tBefore) + " ns.");

		
		System.out.println();
		System.out.println("java.utils.HashMap:");
		memBefore = rt.totalMemory() - rt.freeMemory();
		tBefore = System.currentTimeMillis();
		HashMap<Integer,Integer> hsh = new HashMap<Integer,Integer>(1_250_000);
		tAfter = System.currentTimeMillis();
		System.out.println("Construction took: " + (tAfter - tBefore) + " ms.");
		
		tBefore = System.currentTimeMillis();
		for (int i = 0; i < 1_000_000; ++i)
			hsh.put(randomBuffer[i], randomBuffer[i]);
		tAfter = System.currentTimeMillis();
		memAfter = rt.totalMemory() - rt.freeMemory();
		System.out.println("Used memory estimation: " + (memAfter - memBefore) +
				", average usage per entry: " + (memAfter - memBefore) / 1E6 + " bytes");
		System.out.println("Put average time: " + (tAfter - tBefore) + " ns.");
		
		tBefore = System.currentTimeMillis();
		for (int i = 0; i < 1_000_000; ++i)
			hsh.get(randomBuffer[i]);
		tAfter = System.currentTimeMillis();
		System.out.println("Get average time: " + (tAfter - tBefore) + " ns.");
	}

	public int size() {
		return size;
	}
	
}
